package com.sheng.leetcode.year2022.month11.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/11/22
 *<p>
 * 878. 第 N 个神奇数字<p>
 *<p>
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。<p>
 * 给定三个整数 n , a , b ，返回第 n 个神奇的数字。<p>
 * 因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。<p>
 *<p>
 * 示例 1：<p>
 * 输入：n = 1, a = 2, b = 3<p>
 * 输出：2<p>
 *<p>
 * 示例 2：<p>
 * 输入：n = 4, a = 2, b = 3<p>
 * 输出：6<p>
 *<p>
 * 提示：<p>
 * 1 <= n <= 10^9<p>
 * 2 <= a, b <= 4 * 10^4<p>
 */
public class LeetCode0878 {

    @Test
    public void test01() {
        int n = 1, a = 2, b = 3;
//        int n = 4, a = 2, b = 3;
        System.out.println(new Solution().nthMagicalNumber(n, a, b));
    }
}
class Solution {
    int n, a, b, c;
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public int nthMagicalNumber(int _n, int _a, int _b) {
        /**
         * 被 a 或 b 整除既是满足题意的神奇数字，题目要求获取第 n 个神奇数字
         * 暴力破解：a 和 b 开始分别乘以1,2,3...等数，然后按照从小到大的顺序排好获取第 n 个数字
         * 「容斥原理」：能被 a 或 b 整除的数的个数 = 能够被 a 整除的数的个数 + 能够被 b 整除的数的个数 - 既能被 a 又能被 b 整除的数的个数。
         * n / a + n / b - n / c
         * 其中 c 为 a 和 b 的最小公倍数
         * 求解最小公倍数 lcm 需要实现最大公约数 gcd，两者模板分别为：
         * int gcd(int a, int b) {
         *     return b == 0 ? a : gcd(b, a % b);
         * }
         * int lcm(int a, int b) {
         *     return a * b / gcd(a, b);
         * }
         */
        n = _n; a = _a; b = _b; c = a * b / gcd(a, b);
        long l = 0, r = (long) 1e18;
        while (l < r) {
            // mid 为 l 和 r 的平均数
            long mid = l + r >> 1;
            if (check(mid) >= n) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return (int) (r % 1000000007);
    }
    long check(long x) {
        return x / a + x / b - x / c;
    }
}

//作者：宫水三叶
//        链接：https://leetcode.cn/problems/nth-magical-number/solutions/1984892/by-ac_oier-ln3b/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
